See draft paper.

See MMathPhys oral presentation

Coding theorem connects probability and complexity

AIT differs fundamentally from Shannon information theory because the latter is fundamentally a theory about distributions, whereas the former is a theory about the information content of individual objects (see Descriptional complexity).

If one assumes that the probability of generating a binary input string of length l issimply $2^l$ (which is true for prefix codes, see Appendix A) then the most likely way to obtain output $x$ by random sampling of inputs is with the shortest program that generates it, a string of length $K(x)$.

Direct application of these results fromAIT to many practical systems in science or engineering suf-fers from a number of well known problems:

• $K(x)$ is formally uncomputable (due to halting problem).
• Most results in AIT only hold asymptotically, up to $O(1)$.
• Many of the input-output maps in science and engineering are not UTMs.

The way these problems are tackled is described in the next sections.

Coding theorem for computable functions. We begin with a weaker form of the coding theorem, applicable to real world (computable) functions

$P(x)\leq 2^{-K(x|f,n)+O(1)}$

Eq. (2)

where $K(x|f,n)$ is the complexity of output $x$, given the map $f$ and the value $n$ which is

(see M. Li and P.M.B. Vitanyi. An introduction to Kolmogorov complexity and its applications. Springer-Verlag New York Inc, 2008., and Lecture notes on descriptional complexity and randomness).

We provide a derivation of equation (2) in Appendix B, using standard results from AIT such as: The complexity of a whole set is often much less than the complexity of individual members of the set (9). Informally , $K(x|f, n)$ can be viewed as the length of computer code required to specify $x$, given the function $f$ and value $n$ are already pre-programmed in to the computer. Note that equation (2) is just an upper bound. In contrast to the the full coding theorem of equation (1), there is no lower bound.

We mainly consider maps that comply witha few simple restrictions:

• # inputs $\gg$ # outputs.
• # outpus $\gg 1$, to avoid finite size effects.
• Descriptional complexity of the map $f$ itself doesn't grow with $n$. _{Basically the map is represented by fixed rule-set for computing outputs from inputs, that is largely independently of n.}
• Due to how the algorithmic complexity is approximated in practice, the map needs to be 'well-behaved' in the sense of not producing many outputs like the digit of $\pi$ which are algorithmically simple, but which have large entropy values and thus large values of $\tilde{K}x)$ (the computed approximation of $K(x)$). This is a pratical problem, that depends on the complexity measure we use. The "complexity estimator" they used is described in Appendix F.

If instead the map is allowed to contain arbitrary amounts of information, then the map could assign arbitrary probabilties to the outputs, and any coding theorem-like behaviour would be lost. We discuss this fixed complexity condition further in Appendix C.

as we show in Appendix E , it turns out that a reasonably broad range of complexities will follow under quite general conditions for fixed complexity maps.

They use the above conditions to argue that $K(x|f, n) \approx K(x)$.

Approximately computing $K(x)$. $K(x)$ although uncomputable has been approximated using standard compression algorithms. $\tilde{K}(x)$ is used to denote some real-world (computable) approximation to $K(x)$.

Importance of $O(1)$ terms. Experimental results on apply the coding theorem to short strings suggest that the $O(1)$ terms are not very important.

Central ansatz and simplicity bias:

$P(x)\lesssim 2^{-a\tilde{K}x)-b}$

where the constants $a>0$, and $b$ depend on the mapping, but not on $x$.

We call this upper bound of the probability simplicity bias: High probability outputs must be 'simple', complex outputs must have exponentially lower probabilities. In contrast to the full coding theorem, the lack of a lower bound means that simple outputs may also have low probabilities.

They off estimates for $a$ and $b$ in appendix D. In Appendix B, they also argue that: the upper bound of equation (3) should be tight for most inputs, but weak for many outputs.

Examples of simplicity bias in maps

See them!

Discrete RNA sequence to structure mapping

Coarse-grained ordinary differential equation

Coarse-grained stochastic partial differential equation. Black Scholes equation

Polynomial curves

Random matrix – bias but not simplicity bias

L-systems

Random walk map

Logistic map (see Nonlinear maps)

Predicting which of two outputs has higher probability

Connection to Chomsky hierarchy (see Formal language), Sloppy systems..

Appendix A: AIT

Appendix B: Upper and lower bound for computable maps

Upper bound: following derivation using Shannon-Fano code as in InfoTheory book.

Lower bound: Not sure. Ask!, or read! Page 12.

Also many outputs must have probability below their upper bounds.

Appendix C: Fixed complexity map

Appendix D: Making predictions for P(x) in computable maps

Appendix E: Estimating the range of $K(x|f,n)$.

Arguments based on bounding complexity given the description: map + index of output. This gives upper bounds to min and max complexities to be $0$, and $\log_2{N_0}$ (everything up to additive constant, $O(1)$).

For the max, we also need a lower bound, and this is given by the well known fact in AIT that if one has $N_0$ different strings, not all of them can have complexity lower than $\log_2{N_0}$, as there are not enough such descriptions. In fact, most of the strings need to have a complexity of $\log_2{N_0}$.

Appendix F: Approximations to $K(x)$.

Appendix G: Simplicity bias and system size

Appendix H: On the intuitive connection of probability and complexity

Appendix I: Simplicity bias in the logbinomial distribution

Appendix J: Predicting the number of outputs, $N_0$. By fitting $\alpha$ and estimating $max(K)$ from the known details of the system.

Appendix K: Further examples and figures

Continuous systems are sampled and discretized to create the output.

L-systems, Circadian rhythm

Cell cycle

Feed forward network. Sample networks, measure complexity of given network. by entropy of the distribution of outputs.

Logic gate

Appendix L: Histograms of complexity

An Achlioptas process is a type of Explosive percolation, also known as $m$-edge processes, that involve choosing $m$ candidate edges uniformly at random between any pair of nodes (compare with other Spanning cluster-avoiding process)and applying a rule to select which one is actually chosen. These have been proven to be continuous in the thermodynamic limit, for a fixed $m$. They are generalizations of Erdos-Renyi Random graphs.

The first proposed type, were proposed (in Explosive Percolation in Random Networks) and thought to maybe show a discontinuous phase transition.

Achlioptas processes phase transitions are continuous

It has now been show that the Percolation phase transition for Achlioptas processes (and in fact a more general class of k-vertex rule percolation process) is continuous (in the thermodynamic limit), but very steep (see Explosive Percolation Transition is Actually Continuous and Achlioptas process phase transitions are continuous). One can prove the continuity by looking at the asymptotic effect of removing a single link, as the total size goes to infinity. However, Oliver Riordan and Lutz Warnke proved it by proving, in essence, that the number of subcritical components that join together to form the emergent macroscopic-sized component is not sub-extensive in system size. In the words of Friedman and Landsberg, Achlioptas Processes do not lead to the build-up of a “powder keg" (which is a type of cluster configuration that does lead to discontinuous transitions).

However, the model can be generalized to one that shows genuinely discontinuous transitions (see Anomalous critical and supercritical phenomena in explosive percolation). One way to achieve discontinuity is actually to allow the number of edges in the rule, $m$ to scale up with $N$, the network size, in a certain way.

$2$-edge Achli Achlioptas process is the simplest type: Start with N isolated nodes and add undirected, unweighted edges one at a time. This is done by choosing, at each step, two possible edges uniformly (and independently) at random from the set of $N(N-1)/2$ possible {edges between a pair of distinct nodes}. One adds only one of these edges, making a choice based on a systematic rule that affects the speed of development of a GCC.

$m$-edge rules are defined similarly.

Selection rules

Product rule. One choice that yields "explosive" percolation is to use the so-called "product rule", in which one always retains the edge that minimizes the product of the sizes of the two components that it merges (with an arbitrary choice when there is a tie).

Sum rule. The size of the new component formed is minimized.

Bohman–Frieze (BF) rule. edge 1 is chosen if it joins two isolated vertices, and edge 2 otherwise.

A selection rule can be classified as a bounded-size or an unbounded-size rule. In a bounded-size selection rule, decisions depend only on the sizes of the components and, moreover, all sizes greater than some (rule-specific) constant $K$ are treated identically.

There are also the more general $m$-edge rules based on chosing $m$ edges at each step, and selecting one (or potentially more).

See more rules here: Explosive percolation: Unusual transitions of a simple model

The Evolution of Random Graphs (product rule first suggested here).

Avoiding a giant component. Bounded-size rules are able to switch the percolation threshold.

Birth control for giants. The percolation transition is strongly conjectured to be continuous for all bounded-size rules

Product rule wins a competitive game

Hamiltonicity thresholds in Achlioptas processes

A colloidal particle that is an active system.

Common types are catalytic colloids, that catalyze some reaction, often due to its surface chemical properties or those of a coating. This is often done so that the particle is self-propelling.

See also:

• Phoretic mechanisms of self-propelled colloids
• Collective behaviour of active colloids
• Self-assembly of active colloids
• Boundary effects on the motion of active colloids

Individual and collective behavior of artificial swimmers: "Janus particles"

See Dynamical Instability in Boolean Networks as a percolation Problem, Boolean network

New paper: Network Structure and Activity in Boolean Networks

Activities and Sensitivities in Boolean Network Models

Boolean functions in which few variables have high importance and most other variables have low importance play a role in eliciting order from Boolean networks.

We should mention in passing that much of the discussion in this Letter can be formulated in terms of spectral methods or harmonic analysis on the $n$ cube.

Boolean function derivative

Activity

Sensitivity

For a random Boolean function with bias $p$ (so that each bit in the truth table is $1$ with probability $p$ and $0$ otherwise), the probability that two Hamming neighbors are different is equal to $2p(1-p)$, since one can be $1$ (with probability $p$) and the other 0 (with probability $1-p$), and vice versa.

From this one can see that $E[\alpha_i^f] = 2p(1-p)$, and $E[s^f] = K2p(1-p)$, where $E$ means expectation value w.r.t. the prob. distribution of the truth tables. We can then conclude that highly biased functions ($p$ far away from 0.5) are expected to have low average sensitivity.

For a Boolean function $f$, a canalizing variable is a variable that determines (canalizes) the value of $f$ if it has a given value. See the article for more precise definition. A random Boolean function with a single canalizing variable, it is shown here that the expected activity of the canalizing variable is $1/2$, while that of the rest of the variables is $1/4$

The average sensitivity (when averaged over all the functions in the network) appears to be a good parameter for predicting whether the dynamics of the Boolean network are ordered or chaotic. This can be observed by looking at Derrida curves.

A Process carried out by a sentient being.

They can always be drawn with the vertices arranged so that all edges point downward as in Fig 1. Also all cycles that can be arranged like this are acyclic.

Fig 1.

From the proof of this fact one can deduce an algorithm for finding if a network is acyclic or not:

Furthermore, the adjacency matrix of such a graph can always be made upper-diagonal with zeros on diagonal (as no self-loops). The eigenvalues of an acyclic graph are thus all zero. One can also show the opposite, thus:

Adhesives is any substance applied to one surface, or both surfaces, of two separate items that binds them together and resists their separation.

Some synonyms: glue, cement, mucilage, or paste

Aerosol is a Colloid of fine solid particles or liquid droplets, in air or another gas.

Artificial intelligence

OpenAI - Concrete AI safety problems paper

Algebra (algebraic structure)

Algorithm to compute LZ complexity measure

written in Python

def KC_LZ(string):
    n=len(string)
    s = '0'+string
    c=1
    l=1
    i=0
    k=1
    k_max=1
    stop=0

    while stop==0:
        if s[i+k] != s[l+k]:
            if k>k_max:
                k_max=k # k_max stores the length of the longest pattern in the LA that has been matched somewhere in the SB

            i=i+1 # we increase i while the bit doesn't match, looking for a previous occurence of a pattern. s[i+k] is scanning the "search buffer" (SB)

            if i==l: # we stop looking when i catches up with the first bit of the "look-ahead" (LA) part.
                c=c+1 # If we were actually compressing, we would add the new token here. here we just count recounstruction STEPs
                l=l+k_max # we move the beginning of the LA to the end of the newly matched pattern.

                if l+1>n: # if the LA surpasses length of string, then we stop.
                    stop=1

                else: #after STEP,
                    i=0 # we reset the searching index to beginning of SB (beginning of string)
                    k=1 # we reset pattern matching index. Note that we are actually matching against the first bit of the string, because we added an extra 0 above, so i+k is the first bit of the string.
                    k_max=1 # and we reset max lenght of matched pattern to k.
            else:
                k=1 #we've finished matching a pattern in the SB, and we reset the matched pattern length counter.

        else: # I increase k as long as the pattern matches, i.e. as long as s[l+k] bit string can be reconstructed by s[i+k] bit string. Note that the matched pattern can "run over" l because the pattern starts copying itself (see LZ 76 paper). This is just what happens when you apply the cloning tool on photoshop to a region where you've already cloned...
            k=k+1

            if l+k>n: # if we reach the end of the string while matching, we need to add that to the tokens, and stop.
                c=c+1
                stop=1



    # a la Lempel and Ziv (IEEE trans inf theory it-22, 75 (1976),
    # h(n)=c(n)/b(n) where c(n) is the kolmogorov complexity
    # and h(n) is a normalised measure of complexity.
    complexity=c;

    #b=n*1.0/np.log2(n)
    #complexity=c/b;

Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input

See Algorithms, Data compression

A famous example of Deep reinforcement learning

Mastering the game of Go with deep neural networks and tree search

Two+ Minute Papers - How DeepMind's AlphaGo Defeated Lee Sedol

https://www.reddit.com/r/baduk/comments/49y17z/the_true_strength_of_alphago/

_AofA

Analysis of the Computational complexity of Algorithms, i.e. find out how much time, and how much memory does an algorithm take to run.

Analytic Combinatorics, Part I (Analysis of Algorithms)

Already recognized as important by Babbage, Turing. However, the modern field of analysis of algorithms was started by Donald Knuth, who recognized that mathematics had the tools to analyze algorithms. Things like the following are useful tools for this:

• Recurrence relations
• Generating functions
• Asymptotic analysis

Books: four volumes of The art of computer programming.

Part of the vision of AugMath

3Blue1Brown https://www.youtube.com/watch?v=uXPb9iBDwsw https://www.youtube.com/watch?v=RU0wScIj36o https://github.com/3b1b/manim

Jim Blinn, algebraic ballet

Apollonian gasket (see Apollonian networks)

Apollonian networks online (annotated) pdf

Random Apollonian Networks

Apollonian network

See Apollonian gasket

Topography studies features of the surface of the Earth, as well as other planets. These can be described as landscapes Percolation models and Percolation theory have been applied to understand these.

A landscape is a height profile usually defined on a square lattice where each cell’s elevation value at position x represents the average elevation over the entire footprint of the cell (site). Now imagine that the water is dripping uniformly over the landscape and fills it from the valleys to the mountains, letting the water flow out through the open boundaries. During the raining, watershed lines may also form which divide the landscape into different drainage basins. These are important in geomorphology in e.g., water management [113] and landslide and flood prevention [114]

it is possible to determine the watershed lines based on the iterative application of invasion percolation [115].

Another kind of percolation that can occur: Raising the water level makes lakes join together, and eventually a lake that spans the whole landscape may form. However, whether the percolation transition is critical or not depends on the properties of the surface landscape (in particular on correlation functions).

These ideas have been applied to study the topography of the Earth, where they found that the present sea level is a critical level in their model. This finding elucidates the origins of the appearance of ubiquitous scaling relations observed in the various terrestrial features on Earth.

Arithmetic Compression (Ep 5, Compressor Head) Google

(IC 5.1) Arithmetic coding - introduction

https://www.youtube.com/watch?v=7vfqhoJVwuc

https://www.youtube.com/watch?v=CXCWQy9N2ag

See MMathPhys oral presentation.

Theoretical framework

Following The Arrival of the Frequent: How Bias in Genotype-Phenotype Maps Can Steer Populations to Local Optima (remember notes here are complementary to paper, and don't cover all of its content, only those parts where I thought were gaps for me to understand it), we can study the effect of the structure of the genotype-phenotype (GP) map, in the model of Evolution known as the Wright-Fisher model (see Population genetics). We use the Haploid Wright-Fisher model with selection, where for each individual in the generation at time $t+1$, we choose a single parent from the individuals at the previous generation $t$, according to the rule described there. We then include the effect of mutations, by assigning to the new individual a genotype of length $L$ as follows:

• Copy the genotype of parent.
• For each of the letters in the genotype, replace it with probability $\mu$, the point mutation rate. When you replace, you replace it by a different letter, chosen uniformly at random from the different letters.

Note: the genotype is defined as a sequence of $L$ letters taken from an alphabet of $K$ letters.

See Mean field approximation to average number of phenotypes discovered in Wright-Fisher model , some equations are found there. The main result is that the expected number of individuals with genotype $p$ that arises at generation $t$ can be approximated as

under certain assumptions, explained in that tiddler.

Polymorphic limit

If $NL\mu \gg 1$, the population naturally spreads over different genotypes, a regime called the polymorphic limit. See Polymorphic limit (Wright-Fisher model) tiddler for details. Main points:

To model neutral exploration, we let $1+s_p = \delta_{pq}$, where $\delta_{pq}$ is a Kronecker delta

The time when {{the probability of having discovered a p-type individual (produced a p-type offspring)} is $\alpha$} is found by:

Monomorphic limit

Neutral spaces can be astronomically large, much bigger than even the largest viral or bacterial populations (see this paper). In that case, the local neighborhood of the population may not be fully representative of the neighborhood of the entire space.

This scenario can most easily understood in the monomorphic limit: when mutants are rare, $NL \mu \ll 1$

Now, the (average) rate of neutral mutations (per individual) is $\nu = L \mu \rho$, as $\rho$ is the probability that a mutation is neutral.

See more in the Monomorphic limit (Wright-Fisher model) tiddler, and at the paper.

We can see that in the large genome limit, the phenotype $p$ is found quicker as the population $N$ increases. However, when the population becomes so large that all the 1-mutation neighbourhood is thoroughly explored (while still staying in the monomorphic limit), the discovery time saturates because increasing the population doesn't increase the number of explored phenotypes (during a fixation period).

These results suggest that for intermediate $NL\mu$ there should be a smooth transition between these two regimes. To quantify the crossover we introduce a factor $\gamma$.

[See Figure 1.]

Simulations in model GP maps

The genotype is defined by:

• Alphabet length: $K$
• Genotype length: $L$

The number of available genotypes is thus $K^L$.

Random GP map:

Apart from specifying $K$ and $L$, we need to specify the set $\{F_q\}$ which is the fraction of genotypes mapping to phenotype $p$. The map is otherwise random.

In this setting, $\phi_{pq} = F_p$ is a good approximation if $N_q, N_p \gg 1$, where $N_i$ is the number of genotypes mapping to phenotype $i$. These also require $N_P \ll N_G$ (i.e. {the number of phenotypes } is much less than {the number of genotypes}, i.e the map is very many-to-one).

There is also a percolation threshold at a critical frequency ($F_p$) $\lambda(K) = 1 - K^{-1/(K-1)}$, so that only phenotypes with $F_p > \lambda(K)$ have "completely" connected neutral spaces (in the network where edges correspond to a single-point mutations, or genotypes separated by a Hamming distance of $1$). See the theory of percolation in Network science's Newman's book, Oxford notes, and problem sheets. See also Random Induced Subgraphs of Generalized n-Cubes.

Standing variation. Adaptation from standing genetic variation.

RNA secondary structure mapping

RNA genotypes of length $L$ made up of nucleotides G,C,U and A.

The phenotypes are the minimum free-energy secondary structures for the sequences, which can beefficiently calculated (see Fast Folding and Comparison of RNA Secondary Structures). The number of genotypes grows as $4^L$,while the number of phenotypes is thought to grow roughly as $N_P \sim 1.8^L$ (see Robustness and Evolvability in Living Systems - Andreas Wagner). Also:

From sequences to shapes and back: a case study in RNA secondary structures. - pdf.

Epistasis can lead to fragmented neutral spaces and contingency in evolution

The Ascent of the Abundant: How Mutational Networks Constrain Evolution

Discovery times are slower than in the random GP map. This reflects the internal structure of the RNA: similar genotypes typically have similar mutational neighbourhoods (see Exploring phenotype space through neutral evolution.), and so the population needs to neutrally explore longer in order to find novelty.

Phenotypic bias leads to a simple, systematic ordering in the discovery of novel phenotypes.

The arrival of the frequent

Comment: The fact that this discussion requires speaking about a change in the environment is what makes "the arrival of the frequent" a non-equilibrium effect, I think. Compare this with the survival of the flattest which is an equilibrium effect.

We need to have $s2, s_1\gtrsim 1/(2N)$ because the probability of fixation is (see here (page 201) or here, or here (page 326)):

$P = \frac{1-e^{-qs}}{1-e^{-2Ns}}$

So for $2Ns \gtrsim 1$, $\frac{q(2Ns)}{2N(1-e^{-(2Ns)})} > \frac{q}{2N}$. We need to have $s2, s_1\gtrsim 1/(2N)$ so that the probability of fixation of the two alternative phenotypes is considerably larger than that of the initial phenotype $q$, for which $s=0$. In here (page 321) an expression for the case of $N$ very large is derived without using diffusion approximation.

A more frequent phenotype ($p1$, with $\phi_p1q$ much larger than competitor $p2$) is favoured via two related effects:

• It is discovered much earlier, and so it has a chance to fix before $p2$.
• Because the discovery time-scale is much smaller, if {we are in the large population monomorphic limit, so that the single-mutation neighbourhood is explored many times before population fixes to a new genotype}, then $p1$ is also visited more often. Therefore its fixation probability is larger. Say that $p1$ is visited $n$ times, then the probability that it fixes is $1-(1-p)^n \approx np$, where $p$ is the probability that it fixes when it's visited once ($1/N$ without selection bias), and it is much smaller than $1$ for the approximation ($N$ large). >Isn't this the same as the result that "The rate of fixations is equal to the rate of (neutral) mutations of an individual." derived in Monomorphic limit (Wright-Fisher model)? Yes.This is observed in their microscopic models (On the significance of neutral spaces in adaptive evolution). This effect is ignored in origin-fixation models (see Bias in the introduction of variation as an orienting factor in evolution) Hm, how exactly is it ignored? haven't read the paper yet... Well, from what Ard said, the way they ignore is that they ignore the short-time correlations in the monomorphic limit, discussed in the paper.

Another effect that often positively correlates with the frequency of a phenotype is Mutational robustness (see Robustness and evolvability: a paradox resolved and Epistasis can lead to fragmented neutral spaces and contingency in evolution). Mutational robustness has been shown to offer selective advantage at high mutation rates, because phenotypes which are not robust will often mutate to deleterious mutants and probably go extinct, while phenotypes which are robust will survive. This effect is called the "survival of the flattest", as robust phenotypes correspond to "flat" regions in the fitness landscape (see the paper). This effect can also be understood in terms of free fitness (see Free fitness that always increases in evolution), in analogy to "free energy" in Statistical physics (see The application of statistical physics to evolutionary biology), as it incorporates an entropy-like term accounting for the size of the neutral space of the phenotype.

However, {the arrival of the frequent} is a non-equilibrium effect (unlike {the survival of the flattest} which assumes equilibrium or pseudo-equilibrium). This is because it describes how discovery times and discovery frequency depend on the phenotypes frequency ($F_p$), after a change in the environment, when the system is out-of-equilibrium.

For the monomorphic limit (small mutation rate, in Figure 4.), the probability.....

Summary/Discussion

Genotype-phenotype (GP) maps are observed to be highly biased: Some phenotypes are realised by orders of magnitude more genotypes than most other phenotypes.

Large bias observed in the GP maps translates into a similar order of magnitude variation in the median discovery times $T_p$ for a range of population genetic parameters. However, correlations in the GP map can cause the relation between $T_p$ and phenotype frequency $F_p$ to have large fluctuations (for example, $phi_{pq}$ (which determines $T_p$) can be $0$ even if $F_p$ is quite large).

For the GP mas studied, the strong bias in the GP map leads to a systematic ordering of the median discovery times of alternative phenotypes, an effect that we postulate may hold for other GP maps as well.

The correlations in the RNA GP maps mean that close genotypes have similar neighbourhoods, so that one needs to explore further to reach truly new {genotype neighbourhoods}. This is why the fitting parameter $\gamma$ is smaller than the value expected in the mean-field approx. This is also why for very similar values of $\phi_{pq}4$, there is a range of values of $T_p$ spanning about $1$ order of magnitude. This probably means that it takes up to $\sim 10$ generations to {reach truly novels genotypic neighbourhoods} in the {neutral exploration}. Still, the many orders of magnitude range observed in $\phi_{pq}$ dominates the variation in phenotype discovery times ($T_p$), providing a a posteriori justification for the mean-field approximation.

It is reasonable to expect all these features to arise in other GP maps found in natural (or in artificial systems), including biological systems.

Taken together, these arguments suggest that the vast majority of possible phenotypes may never be found, and thus never fix,even though they may globally be the most fit: Evolutionary search is deeply non-ergodic (I think that this is in the sense that we don't quite reach equilibrium on reasonable time scales, or that the observation time-scales needed for the system to appear ergodic are much larger than those used in experiment. However, this is also true in many other systems like particles in a gas; however, this other system doesn't show the bias needed for the Arrival of the frequent effect).

When Hugo de Vries was advocating for the importance of mutations in evolution, he famously said ‘‘Natural selection may explain the survival of the fittest, but it cannot explain the arrival of the fittest’’ [2]. Here we argue that the fittest may never arrive.Instead evolutionary dynamics can be dominated by the ‘‘arrival of the frequent’’.

Older comments:

So I think what he was talking about is that we can construct a network of phenotypes which is a projection of the network of genotypes via the genotype-phenotype map. Links in the network of genotypes are possible mutations, and all genes have the same degree. However, not all nodes have the same degree in the network of phenotypes.

We can then apply results from network theory of the steady distribution for a random walker on a network.

So this sets a bias on the distribution on the phenotype network.

Over this bias there will be the fitness surface.

Artificial chemistry

http://tuvalu.santafe.edu/~walter/AlChemy/alchemy.html

Arrival of the fittest The modern evolutionary synthesis based on Population genetics has an existence problem: it assumes the existence of individuals, genes, alleles, etc. They propose a simple model abstracting from chemistry to explain the Self-organization of self-maintaining and self-replicating structures, necessary for the origin of life Darwinian Evolution.

They point out related work in autopoiesis, concurrent computation, a "chemical abstract machine", autocatalytic reaction networks.

Review paper

Artificial Chemistries

Writing a Function in Assembly: Intel Att Assembly Stack Part 2

See also Operating system

See Measures and metrics for networks

Homophily or assortative mixing is a bias in favour of connections between network nodes with some similar characteristics.

Assortative mixing by enumerative characteristics

Enumerative (a.k.a categorical) characteristics are those where the possible values don't have any particular metric for being close (i.e. a distance function). Eg.: gender, school

Measure given by modularity:

$Q=\frac{1}{2m}\sum_{ij} \left ( A_{ij}-\frac{k_i k_j}{2m} \right) \delta(c_i, c_j)$

where $\delta(c_i, c_j)$ is the Kronecker delta which is 1 if the category of $i$, $c_i$ is the same as that for $j$, and $0$ otherwise. Another way to write it turns out to be:

$Q=\sum_r (e_{rr}-a_r^2)$

where $e_{rs}$ is the fraction of edges that join nodes of type $r$ to nodes of type $s$, and $a_r$ is the fraction of ends of edges attached to nodes of type $r$. If we generalize to weighted networks then $k$ would be the strength, i.e. the weighted degree; and $e_{rs}$ would be fraction of edge weights joining nodes in the two sets, and $a_r$ would be fraction of half the edge weight assigned to nodes in set $r$.

This is just equal to the number of edges connecting vertices of alike type, minus the expected such number for a random network (with degrees distributions for each category fixed).

$B_{ij} = A_{ij}-\frac{k_i k_j}{2m}$ is called the modularity matrix.

The normalized modularity (normalized by its maximum value when all edges fall between alike edges is called an assortativity coefficient.

Assortative mixing by scalar characteristics

By scalar charactersitics we means does that have a metric that gives a notion of closeness so that two nodes can be approximately alike (age, etc.).

Measure by a Pearson coefficient (i.e. a normalized covariance) for the correlation of the value of the scalar $x_i$ at the two ends of the edge. The covariance turns out to be:

$Q=\frac{1}{2m}\sum_{ij} \left ( A_{ij}-\frac{k_i k_j}{2m} \right) x_i x_j$

and one can divide by its max value to get an assortativity coefficient.

If positive assortativity, sometimes the network is said to be stratified. Others nonlinear kinds of correlations may not be detected by the Pearson coefficient (for example low and high $x$ being more often connected with intermediate $x$). Other information theoretic measures may then be used, or a scatter plot of $x_i$ vs $x_j$ for visual insight, as in figure below:

Note that in this figure, the values, 9, 10, 11, 12 are bins, and the positions of points (which represent edges, or pairs of nodes) within each bin is just used to visually aid in identifying blocks with more density.

Assortative mixing by degree

Degree is special case of scalar because degrees may be close to one another (using usual distance function on integers), so use same formula.

If a network shows assortative mixing by degree, it often displays a core (with high density of nodes) and a periphery (with low) structure See (a). If it shows dissasortative mixing by degree, it often shows star like features and is more uniform See (b).

There appears to be another definition of a quantity called assortativity in this review.

Can also rewrite the assortativity coefficient in this case as a Pearson coefficient for the distribution of the "excess degree" of nodes (i.e. follow an edge to a node and look at distribution of remaining stubs). See page 5 in notes.

Notes:

Given some network and two partitions (assignment of nodes to categories), we can calculate their modularities, and find which is "more modular"

Maximizing $G$ is a good way of finding "communities" of densely-connected nodes with sparse connections between those sets.

Can define scalar measure of assortativity. See page 3 in notes.

See Perturbation methods and Asymptotic approximation

Handout from lecture

Convergence ...

Asymptoticness ..., is often more useful in practice, because truncated series give good results, while convergent series often don't unless you take many terms

Asymptotic approximation (or asymptotic expansion)... An example is an asymptotic power series

See notes for definitions.

Order notation

Big O: $f=O(g)$ as $\epsilon \rightarrow 0$

(f could be asymptotic to const*g, or much smaller)

Small o: $f=o(g)$

f is strictly much less than g

Strict order: $f=\text{ord}(g)$

f is strictly of order g, i.e. asymptotic to some constant times g.

Uniqueness of asymptotic series

If a function posesses an asymptotic approximation in terms of an asymptotic sequence, then that approximation is unique for that particular sequence.

Note that the uniqueness is for a given sequence. A single function may have many asypmtotic approximations, each in terms of a different sequence.

Note also that the uniqueness is for a given function: two functions may share the same asymptotic approximation, because they differ by a quantity smaller than the last term included. Two functions sharing the same asymptotic power series, as above, can only differ by a quantity which is not analytic, because two analytic functions with the same power series are identical.

Asymptotic approximations can be naively added, subtracted, multiplied or divided, resulting in the correct asymptotic expression for the sum, difference, product or quotient, perhaps based on an enlarged asymptotic sequence.

One asymptotic series can be substituted into another, although care is needed with exponentials.

Asymptotic expansions can be integrated term by term with respect to $\epsilon$ resulting in the correct asymptotic expansion of the integral. However, in general they may not be differentiated with safety, i.e., when differentiating there is always the worry that neglected higher-order terms suddenly become important.

Numerical use of divergent series

Optimal truncation: Truncating at the smallest term is known as optimal truncation.

Parametric expansions

So far we have been considering functions of a single variable as that variable tends to zero. Such problems often occur in ordinary and especially partial differential equations when considering far field behaviour for example, and there are known as coordinate expansions.

More common is for the solution of an equation to depend on more than one variable, $f (x; \epsilon$) say. Often we have a differential equation in the independent variable $x$ which contains a small parameter $\epsilon$, hence the name parametric expansion. For functions of two variables the obvious generalisation is to allow the coefficients of the asymptotic expansion to b e functions of the second variable:

$f(x, \epsilon) \sim \sum_{n=0}^\infty a_n(x) \delta(\epsilon)$ as $\epsilon \rightarrow 0$

Integration by parts (IBP)

See examples in notes, and problems.

One has to choose the right functions. Nice because it gives error term explicitly, and can often be bounded.

Trick of separating integral domain.

Failure of integration by parts

General rule: Integration by parts will not work if the contribution from one of the limits of integration is much larger than the size of the integral.

It can still fail in other cases, if for some reason the terms in the expansion can't be generated by the IBP.

Laplace-type integrals

$I(x) = \int_a^b f(t) e^{x\phi(t)} dt$   as $x\rightarrow \infty$

Laplace method

For $\phi(t)$ real. Contributions near global maxima of $\phi(t)$.

Method of stationary phase

For $\phi(t)$ imaginary. Contributions regions of stationary phase $\psi(t)$ (where $\phi(t)=i\psi(t)$).

Method of steepest descents

Most general and powerful. For $\phi(t)$ generally complex, and the integral being along a complex contour in general too.

Splitting range of integration

splitting the range of integration and using different approximations in each range.

See examples

Bounding integrals

Trick I use similar to IBP